#include <iostream>
#include <vector>

using namespace std ;

class Heap
{
public:
    int insert(int v) ;
    int get_max() ;
    void delete_max() ;
    int size() { return m_data.size() ; } ;
private:
    int parent(int x) {  return x< 1 ? -1:(x-1)/2 ;} ;
    int child_left(int x) { return x * 2 + 1 ; } ;
    int child_right(int x) { return x * 2 + 2 ; } ;
    

    void recusive_to_top(int begin_pos) ;
    void recusive_to_bottom(int begin_pos) ;
private:
    vector<int> m_data ;
} ;


int Heap::insert(int v)
{
    m_data.push_back(v) ;
    recusive_to_top(m_data.size()-1) ;
    
}

void Heap::recusive_to_top(int begin_pos)
{
    int pp = parent(begin_pos) ;
    if(pp >=0 && m_data[begin_pos] > m_data[pp])
    {
        swap(m_data[begin_pos],m_data[pp]) ;
        recusive_to_top(pp) ;
    }

}

void Heap::recusive_to_bottom(int begin_pos)
{
    int left = child_left(begin_pos) ;
    if( left < m_data.size() && m_data[left] > m_data[begin_pos])
    {
        swap(m_data[begin_pos],m_data[left]) ;
        recusive_to_bottom(left) ;
    }

    int right = child_right(begin_pos) ;
    if( right < m_data.size() && m_data[right] > m_data[begin_pos])
    {
        swap(m_data[begin_pos],m_data[right]) ;
        recusive_to_bottom(right) ;
    }

}

int Heap::get_max()
{
    if(m_data.size() > 0) return m_data[0] ;
    return -1 ;
}


void Heap::delete_max()
{
    int tail = m_data.size() -1 ;

    if(tail >0) 
    {
        m_data[0] = m_data[tail] ;
        m_data.pop_back() ;
        recusive_to_bottom(0) ;
    }
    else if(tail ==0) m_data.pop_back() ;


}

int main()
{
    Heap heap ;
    heap.insert(4) ;
    heap.insert(1) ;
    heap.insert(3) ;
    heap.insert(9) ;
    heap.insert(2) ;
    heap.insert(9) ;
    heap.insert(11) ;
    heap.insert(1) ;
    heap.insert(111) ;
    heap.insert(1) ;

    while(heap.size() > 0)
    {
        cout << heap.get_max() << endl; 
        heap.delete_max() ;

    }

    return 0 ;
}




